#include "MatrixGraph.h"
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <stdlib.h>

MGraph *builderMGraph() {
    int x, y, w;
    MGraph *mGraph = malloc(sizeof *mGraph);
    printf("请输入顶点数：");
    scanf("%d", &mGraph->nv);
    printf("请输入边数：");
    scanf("%d", &mGraph->ne);

    printf("请输入顶点信息：");
    for (int i = 0; i < mGraph->nv; ++i) {
        char *info = malloc(5 * sizeof *info);
        scanf("%s", info);
        mGraph->data[i].info = info;
        mGraph->data[i].no = i;
    }

    // 初始化邻接矩阵
    for (int i = 0; i < mGraph->nv; ++i) {
        for (int j = 0; j < mGraph->nv; ++j) {
            if (i == j) {
                mGraph->edges[i][j] = 0;
            } else {
                mGraph->edges[i][j] = INT_MAX;
            }
        }
    }

    for (int i = 0; i < mGraph->ne; ++i) {
        printf("请输入边（vi,vj）的上标i，下标j 和权值w：");
        scanf("%d%d%d", &x, &y, &w);
        mGraph->edges[x][y] = w;
        // 无向图，矩阵对称
//        mGraph->edges[y][x] =  mGraph->edges[x][y];
    }

    return mGraph;
}

void deleteMGraph(MGraph *mGraph) {
    if (mGraph != NULL) {
        for (int i = 0; i < mGraph->nv; ++i) {
            free(mGraph->data[i].info);
        }
        free(mGraph);
        mGraph = NULL;
    }
}

// 单源最短路径，Dijkstra 狄克斯特拉算法，适合稀疏图
void dijkstra(MGraph *g, int v) {
    int s[MaxVertexNum], dist[MaxVertexNum], path[MaxVertexNum];
    // 初始化
    for (int i = 0; i < g->nv; ++i) {
        s[i] = 0;
        dist[i] = g->edges[v][i];
        if (g->edges[v][i] < INT_MAX) {
            path[i] = v;
        } else {
            path[i] = -1;
        }
    }
    s[v] = 1;
    path[v] = -1;

    for (int i = 0; i < g->nv; ++i) {
        int u = 0, size = INT_MAX;
        // 找出dist没有访问的最小值和下标
        for (int j = 0; j < g->nv; ++j) {
            if (s[j] == 0 && dist[j] < size) {
                size = dist[j];
                u = j;
            }
        }

        // 标记访问
        s[u] = 1;
        // 遍历没有访问的
        for (int j = 0; j < g->nv; ++j) {
            // 更新当前u结点到各结点的距离
            if (s[j] == 0 && g->edges[u][j] < INT_MAX && g->edges[u][j] + dist[u] < dist[j]) {
                dist[j] = g->edges[u][j] + dist[u];
                path[j] = u;
            }
        }
    }

    // 输出最短路径
    for (int i = 0; i < g->nv; ++i) {
        if (v == i) {
            continue;
        }
        int stack[MaxVertexNum];
        int length = 0;
        int n = i;
        while (n != -1) {
            stack[length++] = n;
            n = path[n];
        }
        if (length > 0) {
            printf("从顶点 %d 到顶点 %d 路径长度为：%2d，路径为：", v, i, dist[i]);
            while (length > 0) {
                if (length == 1) {
                    printf("%d", stack[--length]);
                } else {
                    printf("%d,", stack[--length]);
                }
            }
            printf("\n");
        }
    }
}

// 多源最短路径，Floyd 弗洛伊德算法，适合稠密图
void floyd(MGraph *g) {
    int dist[MaxVertexNum][MaxVertexNum], path[MaxVertexNum][MaxVertexNum];
    // 初始化
    for (int i = 0; i < g->nv; ++i) {
        for (int j = 0; j < g->nv; ++j) {
            dist[i][j] = g->edges[i][j];
            path[i][j] = -1;
        }
    }

    for (int k = 0; k < g->nv; k++) {
        for (int i = 0; i < g->nv; ++i) {
            for (int j = 0; j < g->nv; ++j) {
                if (dist[i][k] < INT_MAX && dist[k][j] < INT_MAX && dist[i][j] > dist[i][k] + dist[k][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                    path[i][j] = k;
                }
            }
        }
    }


    // 输出最短路径
    for (int k = 0; k < g->nv; ++k) {
        for (int i = 0; i < g->nv; ++i) {
            if (k == i) {
                continue;
            }
            int stack[MaxVertexNum];
            int length = 0;
            int n = i;
            while (n != -1) {
                stack[length++] = n;
                n = path[k][n];
            }
            if (length > 0) {
                printf("从顶点 %d 到顶点 %d 路径长度为：%2d，路径为：%d,", k, i, dist[k][i], k);
                while (length > 0) {
                    if (length == 1) {
                        printf("%d", stack[--length]);
                    } else {
                        printf("%d,", stack[--length]);
                    }
                }
                printf("\n");
            }
        }
    }

}

// Prim 普里姆算法
void prim(MGraph *g, int v) {
    int lowcost[MaxVertexNum], closest[MaxVertexNum];
    // 初始化
    for (int i = 0; i < g->nv; ++i) {
        lowcost[i] = g->edges[v][i];
        closest[i] = v;
    }

    for (int i = 1; i < g->nv; ++i) {
        int size = INT_MAX, u = 0;
        // 查找最小权的值
        for (int j = 0; j < g->nv; ++j) {
            if (lowcost[j] != 0 && lowcost[j] < size) {
                size = lowcost[j];
                u = j;
            }
        }
        // 标记访问
        lowcost[u] = 0;

        printf(" 边 (%d, %d)权为: %d\n", closest[u], u, size);
        for (int j = 0; j < g->nv; ++j) {
            // 重新赋值lowcost和closest，u到各顶点的最小权值，这里很巧妙的设计访问过lowcost为0，跳过
            if (g->edges[u][j] != 0 && g->edges[u][j] < lowcost[j]) {
                lowcost[j] = g->edges[u][j];
                closest[j] = u;
            }
        }
    }

}

// 并查集树结点类型
typedef struct {
    int data;
    // 对应的秩
    int rank;
    // 双亲结点
    int parent;
} UFSTTree;

// 初始化并查集树
void makeSet(UFSTTree t[], int n) {
    for (int i = 0; i < n; ++i) {
        t[i].rank = 0;
        t[i].parent = i;
    }
}

// 查找双亲结点
int findSet(UFSTTree t[], int x) {
    if (x != t[x].parent) {
        return findSet(t, t[x].parent);
    } else {
        return x;
    }
}

// 将两个子树合并
void merge(UFSTTree t[], int x, int y) {
    x = findSet(t, x);
    y = findSet(t, y);

    if (t[x].rank > t[y].rank) {
        t[y].parent = x;
    } else {
        t[x].parent = y;
        if (t[x].rank == t[y].rank) {
            t[y].rank++;
        }
    }
}

typedef struct {
    // 边的起始顶点
    int u;
    // 边的终止顶点
    int v;
    // 边的权值
    int w;
} Edge;

void heapSort(Edge e[], int ne) {

}

// kruskal 克鲁斯卡尔算法，适合稀疏图
void kruskal(MGraph *g) {
    UFSTTree t[MaxVertexNum];
    Edge e[MaxVertexNum];
    int k = 1, ei = 1;
    for (int i = 0; i < g->nv; ++i) {
        for (int j = 0; j < g->nv; ++j) {
            if (g->edges[i][j] != 0 && g->edges[i][j] != INT_MAX) {
                e[k].u = i;
                e[k].v = j;
                e[k].w = g->edges[i][j];
                k++;
            }
        }
    }
    // 堆排序
    heapSort(e, g->ne);
    // 初始化并查集树
    makeSet(t, g->nv);
    // 代表当前构造生产树的第几条边，初始化值为1
    k = 1;
    int u, v, sn1, sn2;
    while (k < g->nv) {
        // 取一条边的头尾顶点 u 和 v
        u = e[ei].u;
        v = e[ei].v;
        // 分别得到两个顶点所属集合编号
        sn1 = findSet(t, u);
        sn2 = findSet(t, v);
        // 两顶点属于不同的集合，改边是最小生成树的一条边
        if (sn1 != sn2) {
            printf(" (%d, %d): %d \n", u, v, e[ei].w);
            k++;
            merge(t, u, v);
        }
        ei++;
    }

}


void testMGraph() {
/*    4
    8
    0 1 2 3
    0 1 5
    0 3 7
    1 2 4
    1 3 2
    2 1 3
    2 3 2
    2 0 3
    3 2 1 */
    MGraph *mGraph = builderMGraph();
    printf("==============>>>>>>>>>>>>Dijkstra 狄克斯特拉算法\n");
    dijkstra(mGraph, 0);
    printf("==============>>>>>>>>>>>>Floyd 费洛伊德算法\n");
    floyd(mGraph);
    printf("==============>>>>>>>>>>>>Prim 普里姆算法\n");
    prim(mGraph, 0);
    deleteMGraph(mGraph);
}
